home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / GCcollector.c < prev    next >
C/C++ Source or Header  |  1991-10-21  |  17KB  |  563 lines
  1. /* begincopyright
  2.   Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
  3.   Use and copying of this software and preparation of derivative works based
  4.   upon this software are permitted. Any distribution of this software or
  5.   derivative works must comply with all applicable United States export
  6.   control laws. This software is made available AS IS, and Xerox Corporation
  7.   makes no warranty about the software, its performance or its conformity to
  8.   any specification. Any person obtaining a copy of this software is requested
  9.   to send their name and post office or electronic mail address to:
  10.     PCR Coordinator
  11.     Xerox PARC
  12.     3333 Coyote Hill Rd.
  13.     Palo Alto, CA 94304
  14.     
  15.   Parts of this software were derived from code bearing the copyright notice:
  16.   
  17.   Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  18.   This material may be freely distributed, provided this notice is retained.
  19.   This material is provided as is, with no warranty expressed or implied.
  20.   Use at your own risk.
  21.   
  22.   endcopyright */
  23.  
  24. /*
  25.  * This file contains the functions:
  26.  * void GC_exclusive_mark_inner()
  27.  * void GC_exclusive_mark()
  28.  * XR_Pointer GC_Full_Mark_Inner(self)
  29.  * void GC_full_parallel_mark()
  30.  * XR_Pointer GC_Partial_Mark_Inner(self)
  31.  * void GC_parallel_mark()
  32.  * void GC_asynchronous_mark(which_roots)
  33.  * void GC_freeze_and_start_reclaim()
  34.  * void GC_partial_collection()
  35.  * void GC_full_collection()
  36.  */
  37.  
  38. /*
  39.  * Barry, April 16, 1991 10:26:47 am PST
  40.  * Boehm, May 31, 1991 11:49:24 am PDT
  41.  */
  42.  
  43. # include <signal.h>
  44. # include <sys/types.h>
  45. # include <sys/times.h>
  46. # include <sys/timeb.h>
  47. # include "xr/ThreadsMsg.h"
  48. # include "xr/Threads.h"
  49. # include "xr/GCPrivate.h"
  50. # define CHECK_INVARIANTS
  51. # undef CHECK_INVARIANTS
  52. # define DEBUG_TIMING
  53. # undef DEBUG_TIMING
  54.  
  55. # ifdef CHECK_INVARIANTS
  56. #   include "xr/ThreadsBackdoor.h"
  57. # endif
  58.  
  59. #define I_HOLD_ML(ml) (((XR_ML)(ml))->ml_holder == XR_currThread)
  60.  
  61. static XR_MesaProc ParPartialMarkProc;
  62. static XR_MesaProc ParFullMarkProc;
  63.  
  64. static bool GC_full_gc = FALSE;   /* This is a full collection */
  65.                   /* protected by allocate_ml. */
  66.                   /* Used only for callbacks.  */
  67. static bool GC_clean_roots_marked = FALSE;
  68.                 /* Objects directly reachable from     */
  69.                 /* clean roots have been marked.      */
  70.                 /* Reset to False after mark bits are   */
  71.                 /* cleared.  Not valid while marker is  */
  72.                 /* running.                */              
  73.                   
  74.  
  75. /* Condition variable used to signal end of collection. Protected by */
  76. /* GC_allocate_ml.  Has short timeout.                     */
  77. static struct XR_CVRep gc_done_cv;
  78.  
  79. /* Priority of parallel marker.  Note that it gets woken up periodically */
  80. /* by a much higher priority process.                     */
  81. static XR_Pri gcParallelPriority = XR_PRI_USER_BACKGROUND; /* slightly > IDLE */
  82.  
  83. void GC_full_collection(stop_the_world)
  84. bool stop_the_world;    /* Stop the world during collection, even     */
  85.             /* when not otherwise indicated.        */
  86. {
  87. # ifdef VISUALIZE
  88.     update_message("Full gc");
  89. # endif
  90.  
  91. # ifdef BLACK_LIST
  92.     GC_prepare_to_clear_black_list();
  93. # endif
  94.  
  95.   if (!stop_the_world && GC_should_pre_collect()) {
  96.     GC_partial_collection();
  97.   }
  98.  
  99.     XR_LogVMsg "Starting full marking\n");
  100.  
  101.     GC_reclaim_useful_pages();  /* Must not hold GC_allocate_ml */
  102.     GC_clean_roots_marked = FALSE;
  103.     GC_clear_marks();   /* Safe because of immediately preceding */
  104.                 /* GC_reclaim_useful_pages.         */
  105.     
  106.     GC_revoke_all_tenure();
  107.     GC_tenure_count = 0;
  108.     GC_markCarefully = GC_should_mark_carefully();
  109.   
  110.   /* In parallel mode we just mark all the reachable stuff in parallel,
  111.      and then do a partial collection when it's needed.  */
  112.   if (! stop_the_world && (GC_mode & GC_PARALLEL)) {
  113.     GC_full_parallel_mark();
  114.     GC_partial_collection();
  115.     /* Make entirely empty pages available immediately.  Heap growth    */
  116.     /* is otherwise likely.                        */
  117.     XR_MonitorEntry(&GC_allocate_ml);
  118.     GC_reclaim_empty_pages();
  119.     XR_MonitorExit(&GC_allocate_ml);
  120.   } else {
  121.     /* clearing the dirty bits happens in parallel in
  122.        GC_parallel_mark if we're doing it in parallel, as above. */
  123.     XR_MonitorEntry(&GC_allocate_ml);
  124.     GC_freeze_and_start_reclaim();
  125.     XR_Broadcast(&gc_done_cv);
  126.     GC_reclaim_empty_pages();
  127.     XR_MonitorExit(&GC_allocate_ml);
  128.   }
  129.  
  130.   GC_markCarefully = FALSE;
  131.   GC_max_markfaults = 0;
  132. # ifdef BLACK_LIST
  133.     GC_clear_black_list();
  134. # endif
  135. }
  136.  
  137. void GC_partial_collection()
  138. {
  139.   XR_MonitorEntry(&GC_allocate_ml);
  140.  
  141. # ifdef VISUALIZE
  142.     update_message("Partial gc");
  143. # endif
  144.  
  145.   if (GC_mode & GC_PARALLEL) {
  146.     GC_reclaim_empty_pages();
  147.     GC_parallel_mark();
  148.   }
  149.  
  150.   GC_freeze_and_start_reclaim();
  151.   XR_Broadcast(&gc_done_cv);;
  152.   XR_MonitorExit(&GC_allocate_ml);
  153. }
  154.  
  155.  
  156.  
  157. /*
  158.  * Restore inaccessible objects to the free list or queue them for later
  159.  * reclamation.
  160.  * Update GC_mem_found (number of reclaimed longwords after garbage collection)
  161.  * A call to GC_gcollect actually finishes the reclaim phase of the last
  162.  * collection, and then starts the new collection.
  163.  *
  164.  */
  165. void GC_freeze_and_start_reclaim()
  166. {
  167.     extern void GC_mark_regs();
  168.  
  169. #   ifdef PRINTTIMES
  170.       unsigned long start_faults = GC_check_faults();
  171.       unsigned long start_wall_clock_time = time((time_t *)0);
  172.       /* Times in milliseconds */
  173.     long start_time = 0;
  174.     long flush_time = 0;
  175.     long mark_time = 0;
  176.     long reclaim_time = 0;
  177.     static struct tms time_buf;
  178. #       define FTIME \
  179.          IDIV((100*(time_buf.tms_utime + time_buf.tms_stime)), \
  180.               (LOCAL_HZ/10))
  181.  
  182.       /* Get starting time */
  183.         times(&time_buf);
  184.         start_time = FTIME;
  185. #   endif
  186.  
  187. #   ifdef DIRTY_BITS
  188.     /* Minimize protection violations while the world is stopped. */
  189.     GC_unprotect_headers();
  190. #   endif
  191.  
  192.     /* Finish last collection and update gc counter */
  193. #       ifdef PRINTBLOCKS
  194.         GC_vprintf("\n");
  195. #       endif
  196. #       ifdef PRINTSTATS
  197.       GC_printf("--> Completing collection %d:\n", GC_gc_no);
  198.       GC_vprintf("Reclaimed %d bytes (%d sm. obj. blocks) before flush\n",
  199.             WORDS_TO_BYTES(GC_mem_found), GC_reclaim_count);
  200. #       endif
  201.     GC_reclaim_empty_pages();
  202. #       ifdef PRINTTIMES
  203.       /* Get intermediate time */
  204.         times(&time_buf);
  205.         flush_time = FTIME;
  206. #       endif
  207. #       ifdef PRINTBLOCKS
  208.         GC_vprintf("\n");
  209. #       endif
  210. #       ifdef PRINTSTATS
  211.       GC_printf("Reclaimed total of %d bytes in heap of size %d bytes\n",
  212.             WORDS_TO_BYTES(GC_mem_found), GC_heapsize);
  213.       GC_vprintf("Found %d tenurable blocks\n",
  214.             GC_tenure_count);
  215. #       endif
  216.  
  217.     GC_zero_reclaim_lists();
  218.     
  219.     /* Advance counters for next collection */
  220.     GC_gc_no++;
  221.     GC_full_gc = (GC_my_objects_in_use == 0);  /* No previous marking */
  222.     
  223. #   ifdef PRINTSTATS
  224.       GC_printf("--> Starting %sGC %d after %d allocated bytes\n",
  225.             (GC_full_gc? "full " : ""), GC_gc_no, 4 * GC_words_allocd);
  226. #   endif
  227.     
  228.     GC_mem_found = GC_mem_freed;
  229.     GC_mem_freed = 0;
  230.     GC_words_allocd_before_gc += GC_words_allocd;
  231.     GC_words_allocd = 0;
  232.     GC_objects_allocd_before_gc += GC_objects_allocd;
  233.     GC_objects_allocd = 0;
  234.         
  235. #   ifdef PRINTSTATS
  236.     GC_reclaim_count = 0;
  237. #   endif
  238.  
  239.   /* The only part of the entire garbage collector that needs to be
  240.      run with the world stopped.  But notice that when we're done here
  241.      we have a completely empty heap, and any process that starts up to
  242.      allocate will instantly wedge anyway, since we have the allocation lock.
  243.      Likewise, all of the finalization queues are protected by the allocate
  244.      lock, and we can muck about with the queues in the non-exclusive part
  245.      of the code. */
  246.  
  247.     GC_exclusive_mark();
  248.  
  249. #   ifdef PRINTTIMES
  250.     /* Get intermediate time */
  251.     times(&time_buf);
  252.     mark_time = FTIME;
  253. #   endif
  254.     
  255. #   ifdef PRINTSTATS
  256.     GC_printf("Found %d (atomic) + %d (composite) active bytes\n",
  257.           WORDS_TO_BYTES(GC_my_atomic_in_use),
  258.           WORDS_TO_BYTES(GC_my_composite_in_use));
  259.     GC_vprintf("Bytes recovered before reclaim = %d\n",
  260.               WORDS_TO_BYTES(GC_mem_found));
  261. #   endif
  262.  
  263.   /* Update public statistics to refelect private ones */
  264.       GC_composite_in_use = GC_my_composite_in_use;
  265.       GC_atomic_in_use = GC_my_atomic_in_use;
  266.       GC_objects_in_use = GC_my_objects_in_use;
  267.  
  268.   /* Reclaim large objects and enqueue other blocks for sweeping */
  269.       GC_reclaim();
  270.  
  271. # ifdef PRINTSTATS
  272.     GC_vprintf("Found total of %d bytes by end of initial reclamation\n",
  273.           WORDS_TO_BYTES(GC_mem_found));
  274. # endif
  275.  
  276. # ifdef PRINTTIMES
  277.       times(&time_buf);
  278.       reclaim_time = FTIME;
  279. # endif
  280.  
  281.   if (GC_markfaults > GC_max_markfaults) {
  282.       GC_max_markfaults = GC_markfaults;
  283.   } 
  284.   
  285.   /* Print GC times */
  286. #   ifdef PRINTTIMES
  287.         if (XR_sysArea->sa_numVP == 1) {
  288.       GC_printf(
  289.         "GC took %d(flush) + %d(mark) + %d(ss) msecs\n",
  290.         flush_time - start_time, mark_time - flush_time,
  291.         reclaim_time - mark_time);
  292.     }  /* O.w. numbers probably came from different vps and are bogus */
  293.     GC_vprintf(
  294.         "Elapsed time: %d secs, paused GC faults: %d (%d all marking)\n",
  295.         time((time_t *)0) - start_wall_clock_time,
  296.         GC_check_faults() - start_faults, GC_markfaults);
  297. #   endif
  298.     GC_markfaults = 0;
  299. }
  300.  
  301.  
  302. /*
  303.  * Mark from dirty marked objects, and from roots as
  304.  * specified by which_roots (one of ALL_POINTERS, DEFINITELY_DIRTY_POINTERS,
  305.  * and POSSIBLY_DIRTY_POINTERS).
  306.  * This always preserves the invariant that marked objects on clean
  307.  * pages point to marked objects.
  308.  */
  309. void GC_asynchronous_mark(which_roots)
  310. int which_roots;
  311. {
  312.     int ans;
  313. #   ifdef PRINTTIMES
  314.       unsigned long start_wall_clock_time = time((time_t *)0);
  315. #   endif
  316.    
  317. #   ifdef PRINTSTATS
  318.       GC_printf("--> Starting asynchronous marking for collection %d:\n",
  319.                 GC_gc_no + 1);
  320. #   endif
  321.  
  322.  
  323.     /* Mark from dirty pages */
  324.         /* If this is a full collection there are no marked objects    */
  325.         /* GC_mark_rescuers should just call/return             */
  326.         GC_mark_rescuers(ALIGNMENT);
  327.  
  328.     /* Mark objects reachable from roots */
  329.     /* Get a rough snapshot of the roots.  This is inaccurate, since */
  330.     /* threads are still going.  We assume only that roots we miss   */
  331.     /* that are in the heap will be dirtied when they become      */
  332.     /* interesting, and that anything we get is addressable.     */        
  333.         GC_mark_roots(which_roots);
  334.         GC_mark(ALIGNMENT);
  335.  
  336. #   ifdef PRINTTIMES
  337.     GC_printf("Asynchronous marking took %d seconds\n",
  338.               time((time_t *)0) - start_wall_clock_time);
  339. #   endif
  340. }
  341.  
  342.  
  343. /* Run the parallel marker */
  344. /* Wait for this process to complete before returning.        */
  345. void GC_parallel_mark()
  346. {
  347.     if (!I_HOLD_ML(&GC_allocate_ml)) {
  348.         GC_abort("GC_parallel_mark 0");
  349.     }
  350.     XR_MonitorExit(&GC_allocate_ml);
  351.     GC_RunParallel(ParPartialMarkProc, TRUE);
  352.     XR_MonitorEntry(&GC_allocate_ml);
  353. }
  354.  
  355. /* Run the marking algorithm to clean pages.
  356.    Should only be called via above, I think.  */
  357. XR_Pointer GC_Partial_Mark_Inner(self)
  358. XR_MesaProc self;
  359. {
  360.     unsigned long initial_words_allocd;
  361.     XR_Pri initial_pri = XR_GetPriority();
  362. #   ifdef DEBUG_TIMING
  363.         struct timeval old_t;
  364.         struct timeval mid_t;
  365.         struct timeval new_t;
  366. #   endif
  367.     
  368.     if (I_HOLD_ML(&GC_allocate_ml)) {
  369.         GC_abort("GC_Partial_Mark_Inner 0");
  370.     }
  371.  
  372. #   ifdef DEBUG_TIMING
  373.     XR_GetTimeOfDay(&old_t,0);
  374. #   endif
  375.     GC_lock_to_fixed_vp();
  376. #   ifdef DEBUG_TIMING
  377.     XR_GetTimeOfDay(&mid_t,0);
  378. #   endif
  379.     initial_words_allocd = GC_words_allocd;
  380.     GC_get_and_clear_dirty_bits();
  381. #   ifdef DEBUG_TIMING
  382.     XR_GetTimeOfDay(&new_t,0);
  383.     XR_ConsoleMsg("Acquired dirty bits in %d + %d usecs\n",
  384.                 1000000 * (mid_t.tv_sec - old_t.tv_sec)
  385.                   + mid_t.tv_usec - old_t.tv_usec,
  386.                   1000000 * (new_t.tv_sec - mid_t.tv_sec)
  387.                   + new_t.tv_usec - mid_t.tv_usec);
  388. #   endif
  389.     XR_SetPriority(gcParallelPriority);
  390.         /* After GC_get_and_clear_dirty_bits, to make it easier to get lock. */
  391.     GC_propagate_dirty_bits();
  392.     /* This has to change to get multi-collection tenuring in.
  393.        There are two divisions, tho.  What pages should be searched,
  394.        ??? */
  395.     GC_asynchronous_mark(POSSIBLY_DIRTY_POINTERS);
  396.     if (GC_should_do_second_mark(initial_words_allocd)) {
  397.         XR_SetPriority(initial_pri);
  398.         GC_get_and_clear_dirty_bits();
  399.         XR_SetPriority(gcParallelPriority);
  400.         GC_propagate_dirty_bits();
  401.         GC_asynchronous_mark(DEFINITELY_DIRTY_POINTERS);
  402.     }
  403.     GC_parallel_done();
  404.     return(0);
  405. }
  406.  
  407.  
  408. /* Run a full mark process.  Do not return until it's done. */
  409. void GC_full_parallel_mark()
  410. {
  411.     if (I_HOLD_ML(&GC_allocate_ml)) {
  412.         GC_abort("GC_full_parallel_mark 0");
  413.     }
  414.  
  415.     GC_RunParallel(ParFullMarkProc, TRUE);
  416. }
  417.  
  418.  
  419. /* Run just the marking algorithm, but mark from roots as well.          */
  420. /* Broadcast gc_done_cv when done.                     */
  421. /* Should only be called from the routine above.             */
  422. XR_Pointer GC_Full_Mark_Inner(self)
  423. XR_MesaProc self;
  424. {
  425.     int ans;
  426.     
  427.     if (I_HOLD_ML(&GC_allocate_ml)) {
  428.         GC_abort("GC_Full_Mark_Inner 0");
  429.     }
  430. #   ifdef PRINTSTATS
  431.     GC_printf("--> Starting parallel marking for full collection\n");
  432. #   endif
  433.  
  434.     GC_lock_to_fixed_vp();
  435.     GC_clear_dirty_bits();
  436.     XR_SetPriority(gcParallelPriority);
  437.         /* After GC_clear_dirty_bits, to make it easier to get lock. */
  438.     /* I: "clean marked objects point to marked objects" holds vacuously */
  439.     GC_asynchronous_mark(ALL_POINTERS);
  440.     /* I again holds here. */
  441.     GC_clean_roots_marked = TRUE;
  442.     GC_parallel_done();
  443.     return(0);
  444. }
  445.  
  446.  
  447. void GC_exclusive_mark()
  448. {
  449.   struct GC_InfoRep ir;
  450.   
  451.   /* Run GC_exclusive_mark_inner with all other processes
  452.      stopped.  This is, in a way, the way to aquire the lock on the
  453.      real vm dirty bits.  Nobody else will dirty any pages while we're
  454.      running exclusive.  */
  455.  
  456.     if( !I_HOLD_ML(&GC_allocate_ml) )
  457.         XR_Panic("GC_exclusive_mark 0");
  458.  
  459.     ir.gci_full_collection = GC_full_gc;
  460.     if (GC_callBackBefore != NIL ) {
  461.         (*GC_callBackBefore)(GC_callBackBeforeClientData, &ir);
  462.     }
  463.     GC_RunExclusive( GC_exclusive_mark_inner, 0 );
  464.     if (GC_callBackAfter != NIL ) {
  465.         (*GC_callBackAfter)(GC_callBackAfterClientData, &ir);
  466.     }
  467. }
  468.  
  469. void GC_exclusive_mark_inner()
  470. {    
  471.     if( !GC_running_exclusive )
  472.         XR_Panic("GC_exclusive_mark_inner 0");
  473. #   ifdef CHECK_INVARIANTS
  474.      GC_print_thread_stack(1);
  475. #   endif
  476.  
  477.     /* Correctly set dirty bits.  We clear them way down
  478.        at the bottom, and since we're always running
  479.        alone, and don't dirty any pages of consequence,
  480.        this is as if we had done an atomic GC_get_and_clear_dirty_bits */
  481.  
  482.     GC_get_dirty_bits();
  483.     GC_propagate_dirty_bits();
  484.  
  485.     /* Mark from marked objects on dirty pages */
  486.     GC_mark_rescuers(ALIGNMENT);
  487.     GC_mark_roots(GC_clean_roots_marked?
  488.                   POSSIBLY_DIRTY_POINTERS : ALL_POINTERS);
  489.     GC_clean_roots_marked = TRUE;
  490.     
  491.     /* Roots are now on mark stack.  Mark through them. */
  492.     GC_mark(ALIGNMENT);
  493.     
  494.     /* Finalize */
  495.     /* Doesn't really need to run exclusively.  But the callback does,  */
  496.     /* and this must precede GC_callBackDuring and GC_clear_fl_marks.   */
  497.     /* Not much gets done while we're holding the allocate lock        */
  498.     /* in any case.                            */
  499. #   ifdef FINALIZE
  500.     {
  501. #     ifdef PRINTSTATS
  502.         GC_vprintf("Starting marking for finalization.\n");
  503. #     endif
  504.       GC_TraceFinalizableObjects();
  505.     }
  506. #   endif /* FINALIZE */
  507.  
  508. #ifdef CHECK_INVARIANTS
  509.     GC_printf("Checking invariants...");
  510.     GC_check_invariants_before_reclaim();
  511.     GC_print_thread_stack(1);
  512.     GC_printf("Done checking invariants\n");
  513. #endif
  514.  
  515.  
  516.     /* Clear mark bits for objects on free list, in case they accidentally */
  517.     /* got marked.                                                         */
  518.     GC_clear_free_lists();
  519.     
  520.     if (GC_callBackDuring != NIL ) {
  521.         struct GC_InfoRep ir;
  522.         
  523.         ir.gci_full_collection = GC_full_gc;
  524.         (*GC_callBackDuring)(GC_callBackDuringClientData, &ir);
  525.     }
  526.     
  527.     /* poor name?  Do this if the GC owns the dirty bits? */
  528.     /* Also, since the only things going on between the get and the clear
  529.        are in the marks, [well, alomst the only things] can we just
  530.        make this a GC_get_and_clear_dirty_bits? */
  531.     if (GC_mode & DIRTY_BITS_REQUIRED) { 
  532.         GC_clear_dirty_bits();
  533.     }
  534. }
  535.  
  536. /* Wait for collection to complete, hurrying it along a bit     */
  537. /* Dont wait more than timeout ticks.                */
  538. void GC_wait_for_gc(timeout)
  539. XR_Ticks timeout;
  540. {
  541.     int current_collection = GC_gc_no;
  542.     register XR_Ticks i;
  543.     
  544.     if (timeout == XR_WAIT_FOREVER) timeout = XR_END_OF_TIME;
  545.     GC_start_daemon();
  546.     if( ! I_HOLD_ML(&(GC_allocate_ml)) )
  547.         XR_Panic("GC_wait_for_gc 0");
  548.     for (i = 0; i < timeout; i++) {
  549.         if (GC_gc_no > current_collection) break;
  550.         XR_WaitCV(&gc_done_cv, &GC_allocate_ml);
  551.         if (GC_gc_no == current_collection && (i & 3) == 3) {
  552.             GC_demand_and_dont_wait();
  553.         }
  554.     }   
  555. }
  556.  
  557. void GC_collector_setup()
  558. {
  559.       ParPartialMarkProc = XR_MakeMesaProc(GC_Partial_Mark_Inner, 0);
  560.       ParFullMarkProc = XR_MakeMesaProc(GC_Full_Mark_Inner, 0);
  561.       XR_InitializeCondition(&gc_done_cv, ((XR_Ticks)1));
  562. }
  563.